package com.yiwenup.sorting._02_selection;

import com.yiwenup.sorting.base.Sort;

/**
 * 选择排序
 * 相比冒泡排序，不是每一轮比较都会交换数据
 * 时间复杂度：最好 - O(n²)；最坏 - O(n²)；平均复杂度 - O(n²)
 * 空间复杂度：O(1)
 **/
public class SelectionSort<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void work() {
        for (int end = array.length - 1; end > 0; end--) {
            // 最大值的索引位置
            int idx = 0;
            for (int begin = 1; begin <= end; begin++) {
                if (cmp(idx, begin) <= 0) {
                    idx = begin;
                }
            }
            swap(idx, end);
        }
    }
}
